/**
 * https://leetcode-cn.com/problems/3sum/
 * 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组
 * @param nums 
 */
const threeSum = (nums: number[]): number[][] => {
    const ans: number[][] = []

    const len = nums.length;

    // 长度小于3
    if (len < 3) return ans

    // 排序
    nums.sort((a, b) => a - b)

    /**
     * 找到了和为0的三个数
     */
    const pushAns = (first: number, second: number, last: number) => {
        ans.push([nums[first], nums[second], nums[last]])
    }

    for (let i = 0; i < len; i++) {
        // 跳过这次, 如果一样, i - 1的时候已经组合好了
        if (i > 0 && nums[i] === nums[i - 1]) continue

        let last = len - 1
        // 接下来要找的数字
        let target = -nums[i]
        for (let j = i + 1; j < len; j++) {
            // 如果一样, 跳过这次, [0, 0, 0]
            if (j > i + 1 && nums[j] === nums[j - 1]) continue


            // 如果两个加起来大于要找的数目, last往前
            while(j < last && nums[j] + nums[last] > target) {
                last--
            }
            
            // 到达了边界
            if (j === last) break;
            
            if (target === nums[j] + nums[last]) pushAns(i, j, last)
        }

    }
    return ans
};

console.log(threeSum([-1,0,1,2,-1,-4]))